
//点类
 function Point(_x,_y){
	 
	 this.x=_x;
	this.y = _y;
}
Point.getDistance=function(p1,p2){
		  return  Math.sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}


function DouglasPeucker(points, epsilon,result) {
        // 找到最大阈值点，即操作（1）
        var  maxH = 0;
        var index = 0;
        var end = points.length;
        for (var i = 1; i < end - 1; i++) {
            var  h = H(points[i], points[0], points[end - 1]);
            if (h > maxH) {
                maxH = h;
                index = i;
            }
        }

        // 如果存在最大阈值点，就进行递归遍历出所有最大阈值点
       //  var result = [];
        if (maxH > epsilon) {
            var leftPoints = [];// 左曲线
           var rightPoints =[];// 右曲线
            // 分别提取出左曲线和右曲线的坐标点
            for (var i = 0; i < end; i++) {
				let  p = points[i];
                if (i <= index) {
                    leftPoints.push(p);
                    if (i == index){
                        rightPoints.push(p);
						result.push(p);
						}
                } else {
                    rightPoints.push(p);
                }
            }
       
            // 分别保存两边遍历的结果
            var leftResult = [];
            var rightResult = [];
            leftResult = DouglasPeucker(leftPoints, epsilon,result);
            rightResult = DouglasPeucker(rightPoints, epsilon,result);
        } 
    }



  /**
     * 计算点到直线的距离
     * 
     * @param p
     * @param s
     * @param e
     * @return
     */
    function H(p, s, e) {
        var AB = Point.getDistance(s, e);
        var CB = Point.getDistance(p, s);
        var CA = Point.getDistance(p, e);

        var  S = helen(CB, CA, AB);
        var H = 2 * S / AB;

        return H;
    }

/**
     * 海伦公式，已知三边求三角形面积
     * 
     * @param cB
     * @param cA
     * @param aB
     * @return 面积
     */
  function helen(CB,  CA,  AB) {
        var p = (CB + CA + AB) / 2;
         var S = Math.sqrt(p * (p - CB) * (p - CA) * (p - AB));
        return S;
    }
	

